{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Count Strictly Increasing Subarrays"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #math #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #数学 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: countSubarrays"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #严格递增的子数组个数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个由&nbsp;<strong>正整数&nbsp;</strong>组成的数组 <code>nums</code> 。</p>\n",
    "\n",
    "<p>返回&nbsp;<em><strong>严格递增&nbsp;</strong>顺序的 </em><code>nums</code><em>&nbsp;<strong>子数组&nbsp;</strong>的数目。</em></p>\n",
    "\n",
    "<p data-group=\"1-1\"><strong>子数组&nbsp;</strong>是数组的一部分，且是&nbsp;<strong>连续 </strong>的。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> nums = [1,3,5,4,4,6]\n",
    "<strong>输出:</strong> 10\n",
    "<strong>解释:</strong> 严格递增的子数组如下:\n",
    "- 长度为 1 的子数组: [1], [3], [5], [4], [4], [6]。\n",
    "- 长度为 2 的子数组: [1,3], [3,5], [4,6]。\n",
    "- 长度为 3 的子数组: [1,3,5]。\n",
    "子数组的总数是 6 + 3 + 1 = 10。\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> nums = [1,2,3,4,5]\n",
    "<strong>输出:</strong> 15\n",
    "<strong>解释:</strong> 每个子数组都严格递增。我们可以取 15 个子数组。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= nums[i] &lt;= 10<sup>6</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [count-strictly-increasing-subarrays](https://leetcode.cn/problems/count-strictly-increasing-subarrays/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [count-strictly-increasing-subarrays](https://leetcode.cn/problems/count-strictly-increasing-subarrays/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,3,5,4,4,6]', '[1,2,3,4,5]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int]) -> int:\n",
    "        sisa_lens: List[int] = []\n",
    "        sisa_len: int = 1\n",
    "            \n",
    "        for i in range(1, len(nums)):\n",
    "            if nums[i] > nums[i - 1]:\n",
    "                sisa_len += 1\n",
    "            else:\n",
    "                sisa_lens.append(sisa_len)\n",
    "                sisa_len = 1\n",
    "        sisa_lens.append(sisa_len)\n",
    "        \n",
    "        return sum((1 + n) * n // 2 for n in sisa_lens)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "\n",
    "        res, i = n, 0\n",
    "        while i < n:\n",
    "            j, cnt = i, 0\n",
    "            while j + 1 < n and nums[j] < nums[j + 1]:\n",
    "                j += 1\n",
    "                cnt += 1\n",
    "            res += cnt + cnt * (cnt - 1) // 2\n",
    "            i = j + 1\n",
    "        return res            \n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int]) -> int:\n",
    "        count = 1\n",
    "        pre = 1\n",
    "        for i in range(1, len(nums)):\n",
    "            if nums[i] > nums[i - 1]:\n",
    "                pre += 1\n",
    "            else:\n",
    "                pre = 1\n",
    "            count += pre\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int]) -> int:\n",
    "        cur, res = 1,1\n",
    "        for i in range(1, len(nums)):\n",
    "            if nums[i]<=nums[i-1]:\n",
    "                cur = 1\n",
    "            else:\n",
    "                cur+=1\n",
    "            res+=cur\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "\n",
    "        res, i = n, 0\n",
    "        while i < n:\n",
    "            j, cnt = i, 0\n",
    "            while j + 1 < n and nums[j] < nums[j + 1]:\n",
    "                j += 1\n",
    "                cnt += 1\n",
    "            res += cnt + cnt * (cnt - 1) // 2\n",
    "            i = j + 1\n",
    "        return res            \n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int]) -> int:\n",
    "        temp = 0\n",
    "        allTemp = 1\n",
    "        for i in range(1, len(nums)):\n",
    "            if nums[i] <= nums[i - 1]:\n",
    "                temp = 0\n",
    "            else:\n",
    "                temp += 1\n",
    "            allTemp += temp + 1\n",
    "        return allTemp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int]) -> int:\n",
    "        final_count = 1\n",
    "        count = 1\n",
    "\n",
    "        for i in range(1,len(nums)):\n",
    "            if nums[i] > nums[i-1]:\n",
    "                count += 1\n",
    "            else:\n",
    "                count = 1\n",
    "            final_count += count\n",
    "        return final_count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "\n",
    "        res, i = n, 0\n",
    "        while i < n:\n",
    "            j, cnt = i, 0\n",
    "            while j + 1 < n and nums[j] < nums[j + 1]:\n",
    "                j += 1\n",
    "                cnt += 1\n",
    "            res += cnt + cnt * (cnt - 1) // 2\n",
    "            i = j + 1\n",
    "        return res            \n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int]) -> int:\n",
    "      a = 0\n",
    "      b = 0\n",
    "      pre = inf\n",
    "      for num in nums:\n",
    "        if num > pre: a += 1\n",
    "        else: a = 1\n",
    "        pre = num\n",
    "        b += a\n",
    "      return b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int]) -> int:\n",
    "        res = dp = 0\n",
    "        for i, num in enumerate(nums):\n",
    "            dp = dp + 1 if i == 0 or num > nums[i - 1] else 1\n",
    "            res += dp\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def countSubarrays(self, nums: List[int]) -> int:\r\n",
    "        count = 1\r\n",
    "        pre = 1\r\n",
    "        for i in range(1, len(nums)):\r\n",
    "            if nums[i] > nums[i - 1]:\r\n",
    "                pre += 1\r\n",
    "            else:\r\n",
    "                pre = 1\r\n",
    "            count += pre\r\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int]) -> int:\n",
    "        result, cur, prev = 0, 0, float('inf')\n",
    "        for x in nums:\n",
    "            result += (cur := cur + 1 if prev < x else 1)\n",
    "            prev = x\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int]) -> int:\n",
    "        cur, pre = 0, float('inf')\n",
    "        return sum((cur := cur + 1 if (-pre + (pre := x)) > 0 else 1) for x in nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # 遍历\n",
    "    def countSubarrays1(self, nums: List[int]) -> int:\n",
    "        ans = 1\n",
    "        cur = 1\n",
    "        for x,y in pairwise(nums):\n",
    "            if y > x:\n",
    "                cur += 1\n",
    "            else:\n",
    "                cur = 1\n",
    "\n",
    "            ans += cur\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "    # 遍历2\n",
    "    def countSubarrays(self, nums: List[int]) -> int:\n",
    "        count = 1\n",
    "        pre = 1\n",
    "        for i in range(1, len(nums)):\n",
    "            if nums[i] > nums[i - 1]:\n",
    "                pre += 1\n",
    "            else:\n",
    "                pre = 1\n",
    "\n",
    "            count += pre\n",
    "\n",
    "        return count\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int]) -> int:\n",
    "        count = 1\n",
    "        pre = 1\n",
    "        for i in range(1, len(nums)):\n",
    "            if nums[i] > nums[i - 1]:\n",
    "                pre += 1\n",
    "            else:\n",
    "                pre = 1\n",
    "            count += pre\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int]) -> int:\n",
    "        count = 1  # 因为数组的第一个元素自身就是一个子数组\n",
    "        pre = 1  # 记录前一个数字的严格递增子数组的长度\n",
    "\n",
    "        # 从数组的第二个元素开始遍历\n",
    "        for i in range(1, len(nums)):\n",
    "            # 如果当前元素大于前一个元素，说明它可以构成新的递增子数组\n",
    "            if nums[i] > nums[i - 1]:\n",
    "                pre += 1\n",
    "            # 否则，重置 pre 为1\n",
    "            else:\n",
    "                pre = 1\n",
    "            # 累加 pre 到 count\n",
    "            count += pre\n",
    "\n",
    "        return count\n",
    "\n",
    "# 示例\n",
    "solution = Solution()\n",
    "nums1 = [1,3,5,4,4,6]\n",
    "print(solution.countSubarrays(nums1))  # 输出: 10\n",
    "\n",
    "nums2 = [1,2,3,4,5]\n",
    "print(solution.countSubarrays(nums2))  # 输出: 15\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # 遍利\n",
    "    def countSubarrays1(self, nums: List[int]) -> int:\n",
    "        ans = 1\n",
    "        cur = 1\n",
    "        for x,y in pairwise(nums):\n",
    "            if y > x:\n",
    "                cur += 1\n",
    "            else:\n",
    "                cur = 1\n",
    "\n",
    "            ans += cur\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "    def countSubarrays(self, nums: List[int]) -> int:\n",
    "        count = 1\n",
    "        pre = 1\n",
    "        for i in range(1, len(nums)):\n",
    "            if nums[i] > nums[i - 1]:\n",
    "                pre += 1\n",
    "            else:\n",
    "                pre = 1\n",
    "\n",
    "            count += pre\n",
    "\n",
    "        return count\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # 遍历\n",
    "    def countSubarrays1(self, nums: List[int]) -> int:\n",
    "        ans = 1\n",
    "        cur = 1\n",
    "        for x,y in pairwise(nums):\n",
    "            if y > x:\n",
    "                cur += 1\n",
    "            else:\n",
    "                cur = 1\n",
    "\n",
    "            ans += cur\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "    # 遍历2\n",
    "    def countSubarrays(self, nums: List[int]) -> int:\n",
    "        count = 1\n",
    "        cur = 1\n",
    "        for i in range(1, len(nums)):\n",
    "            if nums[i] > nums[i - 1]:\n",
    "                cur += 1\n",
    "            else:\n",
    "                cur = 1\n",
    "\n",
    "            count += cur\n",
    "\n",
    "        return count\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # 便利\n",
    "    def countSubarrays(self, nums: List[int]) -> int:\n",
    "        ans = 1\n",
    "        cur = 1\n",
    "        for x,y in pairwise(nums):\n",
    "            if y > x:\n",
    "                cur += 1\n",
    "            else:\n",
    "                cur = 1\n",
    "\n",
    "            ans += cur\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        dp=[1]*n\n",
    "        for i in range(1,n):\n",
    "            if nums[i]>nums[i-1]:\n",
    "                dp[i]+=dp[i-1]\n",
    "        return sum(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        dp=[1]*n\n",
    "\n",
    "        for i in range(1,n):\n",
    "            if nums[i]>nums[i-1]:\n",
    "                dp[i]=dp[i-1]+1\n",
    "\n",
    "        \n",
    "        return sum(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        dp=[0]*n\n",
    "        dp[0]=1\n",
    "        for i in range(1,n):\n",
    "            if nums[i]>nums[i-1]:\n",
    "                dp[i]=dp[i-1]+1\n",
    "            else:\n",
    "                dp[i]=1\n",
    "        return sum(dp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        dp=[0]*n\n",
    "        dp[0]=1\n",
    "        for i in range(1,n):\n",
    "            if nums[i]>nums[i-1]:\n",
    "                dp[i]=max(dp[i],dp[i-1]+1)\n",
    "            else:\n",
    "                dp[i]=1\n",
    "        return sum(dp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        dp=[0]*n\n",
    "        dp[0]=1\n",
    "        for i in range(1,n):\n",
    "            if nums[i]>nums[i-1]:\n",
    "                dp[i]=dp[i-1]+1\n",
    "            else:\n",
    "                dp[i]=1\n",
    "        return sum(dp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        dp=[1]*n\n",
    "        for i in range(1,n):\n",
    "            if nums[i]>nums[i-1]:\n",
    "                dp[i]+=dp[i-1]\n",
    "        return sum(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        dp=[1]*n\n",
    "        for i in range(1,n):\n",
    "            if nums[i]>nums[i-1]:\n",
    "                dp[i]+=dp[i-1]\n",
    "        return sum(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        dp=[1]*n\n",
    "        for i in range(1,n):\n",
    "            if nums[i]>nums[i-1]:\n",
    "                dp[i]=dp[i-1]+1\n",
    "        return sum(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int]) -> int:\n",
    "        #因为有无后效性,线性DP即可\n",
    "        n=len(nums)\n",
    "        dp=[1]*n\n",
    "        ans=1\n",
    "        for i in range(1,n):\n",
    "            if nums[i]>nums[i-1]:\n",
    "                dp[i]=dp[i-1]+1\n",
    "            ans+=dp[i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int]) -> int:\n",
    "        #DP\n",
    "        n=len(nums)\n",
    "        dp=[1]*n\n",
    "        ans=1\n",
    "        for i in range(1,n):\n",
    "            if nums[i]>nums[i-1]:\n",
    "                dp[i]=dp[i-1]+1\n",
    "            ans+=dp[i]\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
